package com;

import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YJ
 * Date: 2024-3-10
 * Time: 11:31
 */

class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}


public class mergeTest {
    //合并两个有序链表
    public static ListNode merge(ListNode pHead1,ListNode pHead2) {
        if(pHead1 == null && pHead2 != null) {
            return pHead2;
        }
        if (pHead1!= null && pHead2 == null) {
            return pHead1;
        }
        if (pHead1 == null && pHead2 == null) {
            return null;
        }
        //创建新链表
        ListNode pre = new ListNode(0);
        ListNode newHead = pre;
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        ListNode l = null;
        while(p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                l = new ListNode(p1.val);
                pre.next = l;
                p1 = p1.next;
            } else {
                l = new ListNode(p2.val);
                pre.next = l;
                p2 = p2.next;
            }
            pre = pre.next;
        }
        if (p1 != null) {
            pre.next = p1;
        }
        if (p2 != null) {
            pre.next = p2;
        }
        return newHead.next;
    }

    static ListNode divideMerge(ArrayList<ListNode> lists, int left, int right) {
        if (left > right) return null;
        if (left == right) return lists.get(left);
        int mid = (left + right) >> 1;
        return merge(divideMerge(lists,left,mid),divideMerge(lists,mid + 1,right));
    }
    //
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public static ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        return divideMerge(lists,0,lists.size() - 1);
    }

    public static void main(String[] args) {
        ArrayList<ListNode> lists = new ArrayList<>();
        //1.
        ListNode head1 = new ListNode(-5);
        //2.
        ListNode head2 = new ListNode(-9);
        ListNode list2 = new ListNode(-8);
        ListNode list3 = new ListNode(-7);
        ListNode list4 = new ListNode(-5);
        ListNode list5 = new ListNode(1);
        ListNode list6 = new ListNode(1);
        ListNode list7 = new ListNode(1);
        ListNode list8 = new ListNode(3);
        head2.next = list2;
        list2.next = list3;
        list3.next = list4;
        list4.next = list5;
        list5.next = list6;
        list6.next = list7;
        list7.next = list8;
        //3.
        ListNode head3 = new ListNode(-10);
        ListNode list9 = new ListNode(-7);
        ListNode list10 = new ListNode(-6);
        ListNode list11 = new ListNode(-6);
        ListNode list12 = new ListNode(-6);
        ListNode list13 = new ListNode(0);
        ListNode list14 = new ListNode(1);
        ListNode list15 = new ListNode(3);
        ListNode list16 = new ListNode(3);
        head3.next = list9;
        list9.next = list10;
        list10.next = list11;
        list11.next = list12;
        list12.next = list13;
        list13.next = list14;
        list14.next = list15;
        list15.next = list16;
        //4.
        ListNode head4 = new ListNode(-10);
        ListNode list17 = new ListNode(-8);
        ListNode list18 = new ListNode(-7);
        ListNode list19 = new ListNode(-2);
        ListNode list20 = new ListNode(3);
        ListNode list21 = new ListNode(3);
        head4.next = list17;
        list17.next = list18;
        list18.next = list19;
        list19.next = list20;
        list20.next = list21;
        //5.
        ListNode head5 = new ListNode(-1);
        ListNode list22 = new ListNode(4);
        head5.next = list22;
        //6.
        ListNode head6 = new ListNode(-5);
        ListNode list23 = new ListNode(-4);
        ListNode list24 = new ListNode(-1);
        head6.next = list23;
        list23.next = list24;
        lists.add(head1);
        lists.add(head2);
        lists.add(head3);
        lists.add(head4);
        lists.add(head5);
        lists.add(head6);

        mergeKLists(lists);
    }
}
